package com.study.algorithm.niuke.practice;

import java.util.ArrayList;
import java.util.List;

import static com.study.algorithm.utils.ListUtil.ListOf;

/**
 * 如何得到一个数据流中的中位数？如果从数据流中读出奇数个数值，
 * 那么中位数就是所有数值排序之后位于中间的数值。
 * 如果从数据流中读出偶数个数值，
 * 那么中位数就是所有数值排序之后中间两个数的平均值。
 * 我们使用Insert()方法读取数据流，
 * 使用GetMedian()方法获取当前读取数据的中位数。
 */

public class Median {

    private List<Integer> insertNums;

//    public static void main(String[] args) {
//        Median median = new Median();
//        Scanner scanner = new Scanner(System.in);
//        System.out.println("输入I,开始输入数据，输入99999结束输入：");
//        System.out.println("输入G,获取中位数：");
//        System.out.println("输入QQ,退出");
//        while (scanner.hasNext()) {
//            String nextStr = scanner.next();
//            if (nextStr.toUpperCase().equals("I")) {
//                while (true) {
//                    int nextInt = scanner.nextInt();
//                    if (nextInt == 99999) {
//                        break;
//                    }
//                    median.Insert(nextInt);
//                }
//            }
//            if (nextStr.toUpperCase().equals("G")) {
//                System.out.println(median.GetMedian());
//            }
//            if (nextStr.toUpperCase().equals("QQ")) {
//                break;
//            }
//        }
//    }


    public static void main(String[] args) {
        Median median = new Median();
        List<Integer> integerList = ListOf(1, 8, 3, 2, 7, 9, 35, 74, 56, 332);
        for (int e : integerList) {
            median.Insert(e);
        }
        System.out.println(median.insertNums);
        System.out.println(median.GetMedian());
    }

    public void Insert(Integer num) {
        if (insertNums == null) {
            this.insertNums = new ArrayList<>();
        }
        insertNumsThroughInsertSort(insertNums, num);
    }

    public Double GetMedian() {
        if (insertNums == null || insertNums.size() == 0) {
            return null;
        }
        int size = this.insertNums.size();
        if (size == 1) {
            return insertNums.get(0).doubleValue();
        }

        boolean isOddCount = size % 2 == 1;
        int middleIndex = size / 2;

        if (!isOddCount) {
            return (double) (insertNums.get(middleIndex - 1)
                    + insertNums.get(middleIndex)) / 2;
        }
        return insertNums.get(middleIndex).doubleValue();
    }

    private void insertNumsThroughInsertSort(List<Integer> insertNums, int num) {
        int notNeedInsertIndex = -1;
        int preSize = insertNums.size();
        int gap = 1;
        int insertIndex = findInsertIndexFromBinaryMethod(insertNums, num);
        insertNums.add(num);
        if (insertIndex == notNeedInsertIndex) {
            return;
        }
        backWordMoveWithGap(insertNums, insertIndex, preSize - 1, gap);
        insertNums.set(insertIndex, num);
    }

    private void backWordMoveWithGap(List<Integer> insertNums, int startIndex, int endIndex, int gap) {
        int size = insertNums.size();
        if (endIndex + gap >= size) {
            throw new ArrayIndexOutOfBoundsException("数组越界");
        }
        for (int currIndex = endIndex; currIndex >= startIndex; currIndex -= gap) {
            insertNums.set(currIndex + gap, insertNums.get(currIndex));
        }
    }

    private int findInsertIndexFromBinaryMethod(List<Integer> insertNums, int insertNum) {
        int notNeedInsert = -1;
        int size = insertNums.size();
        int currStartIndex = 0;
        int currEndIndex = size - 1;

        while (true) {
            if (currStartIndex > currEndIndex) {
                return currStartIndex != size ? currStartIndex : notNeedInsert;
            }
            int currIndex = computeNextCompareIndex(currStartIndex, currEndIndex);
            int currVal = insertNums.get(currIndex);

            if (currVal <= insertNum) {
                currStartIndex = currIndex + 1;
            }
            if (currVal > insertNum) {
                currEndIndex = currIndex - 1;
            }
        }
    }

    private int computeNextCompareIndex(int startIndex, int endIndex) {
        return (startIndex + endIndex) / 2;
    }


}
